package com.nuo.laboratory.dataStructure;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * 字符串
 *
 * @author LGC
 * @date 2022/3/24 17:44
 */
public class MyString {


    /**
     * aa
     * aba
     * 最长回文串
     */
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 1) {
            return "";
        }
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = expandAroundCenter(s, i, i);//奇数最长回文串
            int len2 = expandAroundCenter(s, i, i + 1);//偶数最长回文串

            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    /**
     * 中心左右探索最长回文串
     * String str = "babadcad";
     * i = 0  len1 =  1
     * i = 0  len2 =  0
     * i = 0  len = 1, start = 0,end = 0
     * <p>
     * i = 1  len1 =  3
     * i = 1  len2 =  0
     * i = 1  len = 3, start = 0,end = 2
     * <p>
     * i = 2  len1 =  1
     * i = 2  len2 =  0
     * i = 2  len = 1, start = 0, end = 2
     */
    public int expandAroundCenter(String s, int L, int R) {
        while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return R - L - 1;
    }


    /**
     * 获取最长前缀
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length < 1) {
            return "";
        }
        int size = strs.length;
        if (strs.length == 1) {
            return strs[0];
        }

        // 找出字符串最小长度
        int minLen = strs[0].length();
        for (int i = 1; i < size; i++) {
            minLen = Math.min(minLen, strs[i].length());
        }

        StringBuilder sb = new StringBuilder();

        // 循环每一个字符串
        for (int i = 0; i < minLen; i++) {
            char charr = strs[0].charAt(i);
            char temp = strs[1].charAt(i);
            if (temp != charr) {
                break;
            }
            for (int j = 2; j < size; j++) {
                temp = strs[j].charAt(i);
                if (temp != charr) {
                    break;
                }
            }
            if (temp == charr) {
                sb.append(charr);
            }
        }

        return sb.toString();
    }

    public String longestCommonPrefix2(String[] strs) {
        // "abcc", "abc", "abeee"
        if (strs == null || strs.length < 1) {
            return "";
        }
        // 找出字符串最小长度
        int minLen = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            minLen = Math.min(minLen, strs[i].length());
        }
        // 任取一个字符串为公共前缀
        String ans = strs[0];
        for (int i = 0; i < strs.length; i++) {
            // 循环到字符不相等时的下标j，下标j<最小字符串长度，下标j<ans长度
            int j;
            for (j = 0; j < minLen && j < ans.length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            // 截取相同字符
            ans = ans.substring(0, j);
        }

        return ans;
    }


    /**
     * 反转字符串
     *
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        // str = "  a good   boy  "
        String[] split = s.split(" ");
        Stack<String> stack = new Stack<>();
        for (String s1 : split) {
            if (!"".equals(s1)) {
                stack.push(s1);
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
            if (!stack.isEmpty()) {
                sb.append(" ");
            }
        }

        return sb.toString();
    }

    /**
     * 时间滑块
     * 无重复字符的最长子串 =不含有重复字符的 最长子串 的长度
     */
    public static int lengthOfNoRepeatStr(String str) {
        int ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int start = 0, end = 0; end < str.length(); end++) {
            char c = str.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(map.get(c), start);
            }
            map.put(c, end + 1);
            ans = Math.max(ans, end - start + 1);
        }
        return ans;
    }

    /**
     * 只有“(”、")"组成的字符串 是否是有效括号
     * 利用栈
     * 时间复杂度为 O(n)，空间复杂度为 O(n)
     */
    public boolean valid(String str) {
        if (str == null || str.length() < 1) {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                stack.push(')');
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else {
                    stack.pop();
                }
            }

        }
        return stack.isEmpty();
    }

    /**
     * 只有“(”、")"组成的字符串 是否是有效括号
     * 用一个变量计数
     * 时间复杂度为 O(n)，空间复杂度为 O(1)
     */
    public boolean valid2(String str) {
        boolean rs = false;
        if (str == null || str.length() < 1) {
            return true;
        }
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                count++;
            } else {
                if (count == 0) {
                    return false;
                } else {
                    count--;
                }
            }

        }
        return count == 0;
    }


    /**
     * 利用栈
     * 始终保存栈底为 最后一个没有被匹配的右括号的下标
     * 时间复杂度为 O(n)，空间复杂度为 O(n)
     */
    public int longestValidParentheses(String s) {
        // ())((())
        int max = 0;
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.empty()) {
                    stack.push(i);
                } else {
                    max = Math.max(max, i - stack.peek());
                }
            }
        }
        return max;
    }

    /**
     * 利用变量计数
     * 时间复杂度为 O(n)，空间复杂度为 O(1)
     */
    public int longestValidParentheses2(String s) {
        int max = 0, left = 0, right = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                max = Math.max(max, right * 2);
            }
            if (right > left) {
                left = right = 0;
            }
        }
        for (int i = s.length() - 1; i <= 0; i--) {
            if (s.charAt(i) == '(') {
                left++;
            } else {
                right++;
            }
            if (left == right) {
                max = Math.max(max, left * 2);
            }
            if (left > right) {
                left = right = 0;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        // '1' -> 1
        char c1 = '1';
        int num1 = c1 - '0' + 9;
        System.out.println(num1);

        // 1->'1'
        int i = 1;
        char c = 1 + '0';
        System.out.println(c);

        int a = 'a';
        int A = 'A';
        System.out.println(a);
        System.out.println(A);

        // 'a' -> 'A';
        char AA = 'a' - 32;
        System.out.println(AA);

        String str = "abc";

        String substring = str.substring(0, 0);
        System.out.println(substring);

    }


}
